P2922 秘密消息

这道题还是TrieTrie树的板题,先将nn个信息插入字典树中,对于查询的密码,在字典树中查询即可。

插入很好办,我们现在来讨论查询操作。我们记s1s_1为任意一个信息,s2s_2是待匹配的密码。tot[u]tot[u]表示有多少个字符串经过点uufin[u]fin[u]表示有多少个字符串以点uu结尾。

那么会出现三种情况:

阅读全文 »

P3119 Grass Cownoisseur

我们应该用TarjanTarjan缩点,将原图变为GADGAD图,同时记录每个强连通分量的节点个数,记为num[i]num[i]

因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在dis1dis1中(跑正图)和所有点到1的距离存在dis2dis2中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。

题目说可以逆向走一条有向边,我们设该边起点为uu,终点为vv,那么,答案就应为num[belong[1]]+max(dis1[v]+dis2[u])num[belong[1]]+max(dis1[v]+dis2[u])

阅读全文 »

P2341 [HAOI2006]受欢迎的牛

这道题一看就是一道强连通分量的题,不会的可以参考我的博客

当我们用TarjanTarjan缩点之后,记新图点的个数为cntcnt。我们枚举原图的每一条边,计算新图中的点的出度。对于点ii,我们把它的出度记为Out[i]Out[i]。那么,会有以下几种情况:

1.没有一个Out[i]Out[i]为0,说明每一个点至少有一条连向其他边的有向边,那么新图至少有cntcnt条边,一定会有一个环(因为cnt1cnt-1条边是一棵树,无论如何加边都会构成环),但缩点后不可能有环,矛盾。

阅读全文 »

P3469 BLO-Blockade

这道题一看就是到好(shui)题,毕竟自己因long long的问题的错了几次。好吧,不废话,开始讲解:

这道题一看就是求无向图中,去掉一个点后无法连通的点对,但注意:

    阅读全文 »

P2257 YY的GCD

显然,题目求的是:

pprimei=1nj=1m[gcd(i,j)=p]\sum_{p\in prime}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]

阅读全文 »

CF794F Leha and security system

一道神奇的线段树...

题目要求区间修改,区间查询,很容易想到线段树,但是怎么维护每一位数字呢?

显然,我们将每位拆分,对于每一个数字维护他的贡献,如 1221123122112311 的贡献为 10011001001100 , 22 的贡献为 110010110010。于是,我们需要1010棵线段树,维护090-9的贡献。

阅读全文 »

CF480E Parking Lot

显然,如果每次删一个点,答案可能会减小,而且你还不知道在哪里减小的...

所以我们反向思考,如果每次加一个点,那么答案肯定是不减的,而且如果答案变大,新矩阵一定包含该点。

up[i][j]up[i][j]表示以(i,j)(i,j)为起点出发向上能到达的 . '.~' 的个数。(遇到 X 'X~' 停止)

阅读全文 »